package com.azure.code.tree;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/find-duplicate-subtrees/
 * 寻找重复子树
 */
public class FindDuplicateSubTree_652 {
    // 记录所有的子树以及出现的次数
    HashMap<String,Integer> memo = new HashMap<>();
    // 记录重复的子树节点
    LinkedList<TreeNode> res = new LinkedList<>();
    public List<TreeNode> findDuplicateSubtrees(TreeNode root){
        System.out.println(traverse(root));
        return res;
    }

    private String traverse(TreeNode root) {
        if(root==null){
            return "#";
        }
        String left = traverse(root.left);
        String right = traverse(root.right);

        String subStr = left+","+right+","+root.val;
//        System.out.println(subStr);
        int freq = memo.getOrDefault(subStr,0);
        if(freq==1){
            res.add(root);
        }
        memo.put(subStr,freq+1);
        return subStr;
    }

    public static void main(String[] args) {
        TreeNode left = new TreeNode(2,new TreeNode(4),null);
        TreeNode right = new TreeNode(3,new TreeNode(2,new TreeNode(4),null)
                ,new TreeNode(4));
        TreeNode root = new TreeNode(1,left,right);
        System.out.println(new FindDuplicateSubTree_652().findDuplicateSubtrees(root));
    }
}
